#include "iostream"

struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
  ListNode *mergeTwoLists(ListNode *list1, ListNode *list2) {
    ListNode ret{};

    auto head = &ret;

    for (;;) {
      if (list1 == nullptr) {
        head->next = list2;
        break;
      }
      if (list2 == nullptr) {
        head->next = list1;
        break;
      }

      if (list1->val <= list2->val) {
        head->next = list1;
        head = head->next;
        list1 = list1->next;
      } else {
        head->next = list2;
        head = head->next;
        list2 = list2->next;
      }
    }
    return ret.next;
  }
};

int main() {
  ListNode *list1 = new ListNode(1);
  list1->next = new ListNode(2);
  list1->next->next = new ListNode(4);

  ListNode *list2 = new ListNode(1);
  list2->next = new ListNode(3);
  list2->next->next = new ListNode(4);

  Solution s;
  ListNode *ret = s.mergeTwoLists(list1, list2);
  while (ret != nullptr) {
    std::cout << ret->val << " ";
    ret = ret->next;
  }
  std::cout << std::endl;
}